Locating the least 2

摘要A linear program has a unique least 2-norm solution, provided that the linear program has a solution. To locate this solution, most of the existing methods were devised to solve certain equivalent perturbed quadratic programs or unconstrained minimization problems. We provide in this paper a new theory which is different from these traditional methods and is an effective numerical method for seeking the least 2-norm solution of a linear program. The essence of this method is a (interior-point-like) path-following algorithm that traces a newly introduced regularized central path that is fairly different from the central path used in interior-point methods. One distinguishing feature of our method is that it imposes no assumption on the problem. The iterates generated by this algorithm converge to the least 2-norm solution whenever the linear program is solvable; otherwise, the iterates converge to a point which gives a minimal KKT residual when the linear program is unsolvable.

著者Zhao YB, Li D

期刊名稱SIAM Journal on Optimization

出版年份2002

月份4

日期26

卷號12

期次4

出版社Society for Industrial and Applied Mathematics

頁次893 - 912

國際標準期刊號1052-6234

電子國際標準期刊號1095-7189

語言英式英語

關鍵詞least 2-norm solution; linear programming; path-following algorithm; regularized central path

Web of Science 學科類別Mathematics; Mathematics, Applied; MATHEMATICS, APPLIED